package leetcode.editor.cn;

import java.util.Arrays;

class MaximumLengthOfRepeatedSubarray {
    public static void main(String[] args) {
        Solution solution = new MaximumLengthOfRepeatedSubarray().new Solution();
        solution.findLength(new int[]{1, 2, 3, 2, 1}, new int[]{3, 2, 1, 4, 7});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 动态规划（二维数组）
         *
         * @param nums1
         * @param nums2
         * @return
         */
//        public int findLength(int[] nums1, int[] nums2) {
//            // dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
//            int[][] dp = new int[nums1.length + 1][nums2.length + 1];
//            int result = 0; // 记录最大的重复数组长度
//            dp[0][0] = 0;   // 初始化，如果dp[0][0]初始化为1，那么dp[1][1] = dp[0][0] + 1 = 2，此时的下标还是0(1 - 1)，所以不满足题意
//
//            for (int i = 1; i <= nums1.length; i++) {
//                for (int j = 1; j <= nums2.length; j++) {
//                    if (nums1[i] == nums2[j]) { // 如果相等，才是重复的数组
//                        dp[i][j] = dp[i - 1][j - 1] + 1;    // 等于前一个重复的数字加一
//                    }
//                    if (dp[i][j] > result) result = dp[i][j];
//                }
//            }
//
//            return result;
//        }

        /**
         * 滚动数组
         *
         * @param nums1
         * @param nums2
         * @return
         */
        public int findLength(int[] nums1, int[] nums2) {
            int[] dp = new int[nums1.length + 1];
            int result = 0;
            Arrays.fill(dp, 0);

            for (int i = 1; i <= nums1.length; i++) {
                for (int j = nums2.length; j > 0; j--) { // 需要倒的遍历，和背包问题中的滚动数组一致，以免覆盖前面的元素
                    if (nums1[i - 1] == nums2[j - 1]) {
                        dp[j] = dp[j - 1] + 1;
                    } else {
                        dp[j] = 0;  // 赋值为0
                    }
                    if (dp[j] > result) result = dp[j];
                }
            }

            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}

